//对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。 
//
// 给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。 
//
// 
//
// 示例 1： 
//
// 
//输入：str1 = "ABCABC", str2 = "ABC"
//输出："ABC"
// 
//
// 示例 2： 
//
// 
//输入：str1 = "ABABAB", str2 = "ABAB"
//输出："AB"
// 
//
// 示例 3： 
//
// 
//输入：str1 = "LEET", str2 = "CODE"
//输出：""
// 
//
// 
//
// 提示： 
//
// 
// 1 <= str1.length, str2.length <= 1000 
// str1 和 str2 由大写英文字母组成 
// 
//
// Related Topics 数学 字符串 👍 383 👎 0

package leetcode.editor.cn;
//java:字符串的最大公因子
public class Q1071GreatestCommonDivisorOfStrings {
    public static void main(String[] args){
        Solution solution = new Q1071GreatestCommonDivisorOfStrings().new Solution();
        solution.gcdOfStrings("LEET", "CODE");
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (str1 == null || str1.length() == 0 || str1.length() > 1000
                || str2 == null || str2.length() == 0 || str2.length() > 1000) return null;
        int n = Math.min(str1.length(), str2.length());
        // 因为求的是最大公约数，所以可以从大到小进行遍历
        for (int i = n; i >= 0; i--) {
            String pattern = str1.substring(0, i);
            if (check(str1, pattern) && check(str2, pattern)) return pattern;
        }
        return "";
    }

    public boolean check(String s, String pattern) {
        if (pattern.length() == 0 || s.length() % pattern.length() != 0) return false;
        StringBuffer sb = new StringBuffer();
        while (sb.toString().length() < s.length()) {
            sb.append(pattern);
            if (sb.toString().equals(s)) return true;
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}